// 4.希尔排序
// 希尔排序法的平均时间复杂度是 O(n^(1.3-2))    n^1.3~n^2
// 思路：

//  比如下面的数字, 81, 94, 11, 96, 12, 35, 17, 95, 28, 58, 41, 75, 15.
//  我们先让间隔为 5, 进行排序. (35, 81), (94, 17), (11, 95), (96, 28), (12, 58), (35, 41), (17, 75), (95, 15)
//  排序后的新序列, 一定可以让数字离自己的正确位置更近一步.
//  我们再让间隔位 3, 进行排序. (35, 28, 75, 58, 95), (17, 12, 15, 81), (11, 41, 96, 94)
//  排序后的新序列, 一定可以让数字离自己的正确位置又近了一步.
//  最后, 我们让间隔为 1, 也就是正确的插入排序. 这个时候数字都离自己的位置更近, 那么需要复制的次数一定会减少很多.

// 选择合适的增量:

//  在希尔排序的原稿中, 他建议的初始间距是 N / 2, 简单的把每趟排序分成两半.
//  也就是说, 对于 N = 100 的数组, 增量间隔序列为: 50, 25, 12, 6, 3, 1.
//  这个方法的好处是不需要在开始排序前为找合适的增量而进行任何的计算.
//  我们先按照这个增量来实现我们的代码.
function shellSort(arr) {
  let length = arr.length;
  let gap = Math.floor(length / 2); //增量
  while (gap > 0) {
    // 插入排序
    for (let i = gap; i < length; i++) {
      // 保存临时变量
      let j = i;
      let temp = arr[i];
      while (j > gap - 1 && arr[j - gap] > temp) {
        arr[j] = arr[j - gap];
        j -= gap;
      }
      arr[j] = temp;
    }
    gap = Math.floor(gap / 2); //更新增量
  }
  return arr;
}

const test = [765, 234, 547, 241, 62, 124, 6, 232, 3, 2];
console.log(shellSort(test));
